package struct.arrays;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: kanggw
 * @date: 2022/2/25
 * @DESCRIPTION:　
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 * 说明：
 *
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

 */
public class OneCountNumber {

    public static void main(String[] args) {
        int[] arr = {2, 2, 1, 3, 3};

        //myself(arr);
        bitOperation(arr);

    }

    public static void myself(int[] arr) {
        //时间复杂度　nxn

        final List<Integer> arrayList = new ArrayList<>();

        for (int i = 0; i < arr.length; i++) {
            if (arrayList.contains(arr[i])) {
                arrayList.remove(arrayList.indexOf(arr[i]));

            } else {
                arrayList.add(arr[i]);
            }
        }

        arrayList.forEach(item -> {
            System.out.println("out:" + item);
        });
    }

    /**
     * 按位异或^(bitwise exclusive OR)
     * 当两位相异时，结果为1
     * e.g. 1^1=0, 1^0=1, 0^1=1, 0^0=0
     * 可以简单的理解为不进位加法,1+1=0, 0+0=0, 1+0=1, 0+1=1
     * 任意一位，和0异或操作不变，和自身异或操作为0
     * 对于任何数,都有A^0=A A^A=0
     * 自反性：A^B^A=B^0=B
     */
    public static void bitOperation(int[] arr) {

        int result = 0;
        for (int i = 0; i < arr.length; i++) {
            result ^= arr[i];
        }
        System.out.println("bitOperation:" + result);


    }

}
